/**
 * 相邻数位绝对值恰好是1的数的数量
 * 设D[110][10]即可
 * Dij中的j表示上一位是j的情况，过滤条件可以直接过滤
 */

using llt = long long;
llt const MOD = 1E9 + 7;
vector<int> G;
// 均是过滤条件，可以不用额外的状态
llt D[120][10];
llt dfs(int pos, int pre, bool lead, bool limit){
    if(-1 == pos) {
        return 1;
    }
    if(not lead and not limit and -1 != D[pos][pre]) {
        return D[pos][pre];
    }
    int last = limit ? G[pos] : 9;
    llt ans = 0;
    for(int i=0;i<=last;++i){
        if(lead){
            if(0 == i){
                ans += dfs(pos - 1, 0, true, limit&&last==i);
            }else{
                ans += dfs(pos - 1, i, false, limit&&last==i);
            }
        }else if(i - 1 == pre or i + 1 == pre){
            ans += dfs(pos - 1, i, false, limit&&last==i);
        }
        ans %= MOD;
    }
    if(not lead and not limit){
        D[pos][pre] = ans;
    }    
    return ans;
}

llt digitDP(const string & s){
    G.clear();
    for(int i=s.length()-1;i>=0;--i){
        G.emplace_back(s[i] - '0');
    }
    return dfs(G.size()-1, 0, true, true);
}

class Solution {
public:
    int countSteppingNumbers(string low, string high) {
        memset(D, -1, sizeof(D));
        // 先将low减一
        int k = low.length() - 1;
        while(k >= 0 and low[k] == '0') k -= 1;
        low[k] -= 1;
        for(int i=k+1;i<low.length();++i) low[i] = '9';
        return ((digitDP(high) - digitDP(low)) % MOD + MOD) % MOD;     
    }
};